#include <iostream>
#include <stack>
#include <vector>
#include "../head/struct.h"

using namespace std;

// 144
/**
 * 二叉树的前序遍历，使用栈非递归遍历
 * 经典二叉树非递归前序遍历
 * 时间复杂度: O(n), n为树的节点个数
 * 空间复杂度: O(h), h为树的高度	
 */
class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> res;
        if(root == NULL)
            return res;

        stack<TreeNode*> stack;
        stack.push(root);
        while(!stack.empty()){
            TreeNode* curNode = stack.top();
            stack.pop();
            res.push_back(curNode->val);

            if(curNode->right)
                stack.push(curNode->right);
            if(curNode->left)
                stack.push(curNode->left);
        }
        return res;
	}
};

int main(){}
